반복에서 재귀로: 사고의 재구성

재귀(Recursion)는 문제 해결 방식을 본질적으로 변화시키는 방법론입니다. 리스트 합계와 같은 문제를 다룰 때,반복법(코드 목록 4-2)는 명시적인 누산기 theSum 와 반복 상태 제어에 의존하지만, 재귀법은 깊이 있는 수학적 정의에 의존합니다:

재귀는 단순히 함수가 자신을 호출하는 것을 넘어서, 복잡한 문제를 그 구조와 동일한 더 작은 하위 문제로 분해합니다. 핵심은 큰 문제와 하위 문제 사이의자기 유사성을 인식하는 데 있습니다. 재귀 실행은 두 개의 대칭 단계로 구성됩니다:

• “내려가는” 단계: 리스트를 계속해서 자르고 호출 스택에 쌓아, 해결할 수 있는기본 사례(Base Case)에 도달할 때까지입니다.
• “돌아오는” 단계: 가장 간단한 상태부터 시작하여 계층적으로 위로 반환하면서 결과를 병합합니다.